public class PartitionLinkList86 {

    /**
     *
     * 86分隔链表
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     *
     *输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
     *
     *
     * @param args
     */
    public static void main(String[] args) {

        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();

        linkedListQueue.enqueue(1);
        linkedListQueue.enqueue(4);
        linkedListQueue.enqueue(3);
        linkedListQueue.enqueue(2);
        linkedListQueue.enqueue(5);
        linkedListQueue.enqueue(2);
        LinkedListQueue<Integer>.Node partition = partition(linkedListQueue, 3);

        System.out.println("-----");


    }

    public static LinkedListQueue<Integer>.Node partition(LinkedListQueue<Integer> head, int x) {
        // 存放小于 x 的链表的虚拟头结点
        LinkedListQueue<Integer> dummy1 = new LinkedListQueue();
//        dummy1.enqueue(-1);
        // 存放大于等于 x 的链表的虚拟头结点
        LinkedListQueue<Integer> dummy2 = new LinkedListQueue();
//        dummy2.enqueue(-1);
        LinkedListQueue<Integer>.Node p1 = dummy1.getHead();


        LinkedListQueue<Integer>.Node p2 = dummy2.getHead();

        LinkedListQueue<Integer> p3 = head;

        LinkedListQueue<Integer>.Node p = head.getHead();
        while (p != null) {
            if (p.e >= x) {
                p2.e = x;
                p2.next = p;
                p2 = p2.next;
            } else {
                p1.e = x;
                p1.next = p;
                p1 = p1.next;
            }
            // 断开原链表中的每个节点的 next 指针
            LinkedListQueue<Integer>.Node temp = p.next;
            p.next = null;
            p = temp;
        }

        // 连接两个链表
        p1.next = dummy2.getHead();
        return dummy1.getHead();

    }


}
